package algo_lignes_sites.data.pre_trt.pre_trt_path;

import algo_lignes_sites.data.junction.A_Junction;
import algo_lignes_sites.data.junction.A_Junction.TypeJunction;
import algo_lignes_sites.data.junction.JunctionDER;
import algo_lignes_sites.data.junction.JunctionREF;
import algo_lignes_sites.data.path.A_Path;
import algo_lignes_sites.data.path.PathREF;
import algo_lignes_sites.params.Params_ls;
import commons.logs.Logger;
import commons.spatialindex.simplegrid.SimpleGridSPI;
import commons.utils.UtilsGeom;
import commons.utils.primitive_geom.Rect_d;
import gnu.trove.list.array.TIntArrayList;
import gnu.trove.set.hash.THashSet;
import gnu.trove.set.hash.TIntHashSet;
import java.util.ArrayList;


public class SimplifTracePath {

	private static ArrayList<PathREF> vAllPathREF;
	private static ArrayList<PathREF> vPathREFaTraiter;
	private static THashSet<PathREF> setPathREFMalReduit;
	private static ArrayList<JunctionREF> vAllJunctionREF;
	private static Params_ls params;
	private static SimpleGridSPI spiPath;
	private static double tolerance_reel_m_MAX;
	
	private static boolean bDuringTrt;


	// Renvoie la liste des Path qui n'ont pas eu une simplification totale
	//  et qu'il conviendra peut être de reprendre dans une autre passe
	public static ArrayList<PathREF> simplifyTracePath(ArrayList<PathREF> vAllPathREF, ArrayList<PathREF> vPathREFToSimplify, ArrayList<JunctionREF> vAllJunctionREF, Params_ls params, SimpleGridSPI spiPath) {
		Logger.log_INFO1("-- Simplification du tracé des Path --");
		Logger.log_INFO2(" -> Nb. path a simplifier : " + vPathREFToSimplify.size());
		if (params.factor_SimplifPath_tolerance <= 0) {
			Logger.log_INFO2("  -> rien à simplifier : tolérence = 0");
			return new ArrayList<PathREF>();
		}
		
		SimplifTracePath.vAllPathREF = vAllPathREF;
		SimplifTracePath.vPathREFaTraiter = vPathREFToSimplify;
		SimplifTracePath.vAllJunctionREF = vAllJunctionREF;
		SimplifTracePath.params = params;
		SimplifTracePath.bDuringTrt = false;
		
		// SPI pour la recherche d'intersections résiduelles
		SimplifTracePath.spiPath = spiPath;
		spiPath.clear();
		spiPath.addObjects(vAllPathREF);
		
		SimplifTracePath.setPathREFMalReduit = new THashSet<PathREF>();
		
		reducPath();
		clear();
		
		// On renvoie les path qui n'ont pas été réduit completement
		ArrayList<PathREF> vRes = new ArrayList<PathREF>();
		vRes.addAll(setPathREFMalReduit);
		return vRes;
	}
	
	
//	// Le SpiPathDER contient les path DER et doit être pré-rempli !
//	public static void simplifyTracePath_duringTrt(ArrayList<PathREF> vAllPathREF, ArrayList<PathREF> vPathREFToSimplify, ArrayList<JunctionREF> vAllJunctionREF, Params_ls params, SimpleGridSPI spiPathDER) {
//		Logger.log_INFO1("-- Simplification du tracé des Path durant le traitement --");
//		Logger.log_INFO2(" -> Nb. path a simplifier : " + vPathREFToSimplify.size());
//		if (params.factor_SimplifPath_tolerance <= 0) {
//			Logger.log_INFO2("  -> rien à simplifier : tolérence = 0");
//			return;
//		}
//		
//		SimplifTracePath.vAllPathREF = vAllPathREF;
//		SimplifTracePath.vPathREFaTraiter = vPathREFToSimplify;
//		SimplifTracePath.vAllJunctionREF = vAllJunctionREF;
//		SimplifTracePath.params = params;
//		
//		// SPI pour la recherche d'intersections résiduelles
//		SimplifTracePath.spiPath = spiPathDER;
//		
//		reducPath();
//
//		clear();
//	}


	
	
	public static void redecoupPath(ArrayList<PathREF> vAllPathREF, ArrayList<PathREF> vPathREFToRedecoupe, ArrayList<JunctionREF> vAllJunctionREF, Params_ls params, SimpleGridSPI spiJunction) {
		Logger.log_INFO1("-- Redecoupage des Path --");
		
		SimplifTracePath.vAllPathREF = vAllPathREF;
		SimplifTracePath.vPathREFaTraiter = vPathREFToRedecoupe;
		SimplifTracePath.vAllJunctionREF = vAllJunctionREF;
		SimplifTracePath.params = params;
		SimplifTracePath.bDuringTrt = true;
		
		// SPI uniquement pour tester si les points qu'on rajoute n'existent pas déjà
		spiJunction.clear();
		spiJunction.addObjects(vAllJunctionREF);

//		redecoupePath_procheNode(spiJunction/*, vPathREFToRedecoupe, vAllJunctionREF*/);
		redecoupePath_std();
		redecoupePath_procheNode(spiJunction);
		// nouveauté, permettant dans le cas de nodes reliés par 2 path de voir ces 2 path s'écarter correctement
		//  a l'aide des diverses reduction d'atténuation de force de répulsion et d'entrainement
		//  mais pour que ca marche, il faut un minimum de junction entre les nodes
		// Attention, cette fonction ne MAJ pas le SPI avec les nouvelles junctions !!
		redecoupeAllPath_NodeNode();

		clear();
	}


	// Détruit les objets éventuellement créés par ce module et supprime les liens statiques avec les objets passés en paramètres
	private static void clear() {
		vAllPathREF = null;
		vPathREFaTraiter = null;
		vAllJunctionREF = null;
		spiPath = null;
	}

	//**************************************************************************
	//**************************************************************************

	private static void reducPath() {
		Logger.log_INFO2(" -> Réduction Douglas-Peucker, tolérance = " + params.factor_SimplifPath_tolerance + " x épaisseur_Path");

		SimplifTracePath.tolerance_reel_m_MAX = params.getLargestPath_papier_mm()*params.factor_SimplifPath_tolerance/1000.0 * (1/params.echelleCible);

		// apres les Path vont évoluer au fil des simplifications, mais on ne
		// recalculera pas les segments et on ne recalculera pas le SPI, car ils bougeront peu
		// pour se prémunir d'erreur, on grossira chaque rect englobant de 2 tolerence max :
		//  une pour l'objet de base, et une pour les objets recherchés dans le SPI
		//  de sorte de toujours récupérer les Path intersectant potentiellement un segment

		// Precalcul du bounding box du path, utilisé que pour la Simpliftrace path, elle permettra des optim
		//  pour la recherche d'intersection
		for (PathREF path : vAllPathREF)
			path.computeBoundingBox();

		for (PathREF path : vPathREFaTraiter) {
			
			// Découpage du Path en PPS
			ArrayList<PortionPathASimplifier> vPPS = decomposePathEnPPS(path);
			if (vPPS == null) return;
			Logger.log_DEBUG2("Simplification Path : " + path + "  ->  " + vPPS.size() + " parties à simplifier");


			// Set des index des points du path que l'on va conserver
			TIntHashSet setAllIndexPointToKeep = simplifyAllPpsOfPath(vPPS);

			// A present on dispose de l'ensemble des index de points à conserver
			// on reconstitue son vecteur de junctions
			ArrayList<JunctionREF> old_vJREF = path.getVJunctionREF();
			ArrayList<JunctionREF> new_vJREF = new ArrayList<JunctionREF>();
			for (int i=0; i<old_vJREF.size() ; i++) {
				if (setAllIndexPointToKeep.contains(i))
					new_vJREF.add(old_vJREF.get(i));
			}
			path.setVJunctionREF(new_vJREF);
			
			// Si on se trouve en phase durant le traitement, on doit appliquer la même simplification au pathDER correspondant
			// On doit reconstituer les segments (pas encore créés en phase de pretraitement)
			if (bDuringTrt) {
				ArrayList<JunctionDER> old_vJDER = path.getPathDER().getVJunctionDER();
				ArrayList<JunctionDER> new_vJDER = new ArrayList<JunctionDER>();
				for (int i=0; i<old_vJDER.size() ; i++) {
					if (setAllIndexPointToKeep.contains(i))
						new_vJDER.add(old_vJDER.get(i));
				}
				path.getPathDER().setVJunctionDER(new_vJDER);				
			}
			
		}

		// Maintenant que les Path ont été simplifiés, certaines JunctionREF, présentes
		//  dans le vecteur global vJunction sont à supprimer, d'où
		// Nettoyage du vecteur global vJunction : on ne garde que celle qui sont référencées
		//  au moins une fois dans un des path + les nodes (car il peut y avoir des nodes isolés)
		JunctionREF.cleanVJunctionREFGlobal(vAllPathREF, vAllJunctionREF);
	}


	private static TIntHashSet simplifyAllPpsOfPath(ArrayList<PortionPathASimplifier> vPPS) {
		// Ensemble des points que l'on va conserver du path
		TIntHashSet setAllIndexPointToKeep_4path = new TIntHashSet();

		int nbPPS = vPPS.size();
		for (int i=0 ; i<nbPPS ; i++) {

			PortionPathASimplifier pps = vPPS.get(i);

			if (simplifyPPS (pps, vPPS, spiPath)) {
				// La simplification de la pps a réussi, on ajoute les points à conserver dans le set global du path
				Logger.log_DEBUG2("  -> la portion " + pps + " a été simplfiée , reduction pt =  " + (pps.iFin-pps.iDeb+1) + " -> " + pps.vIndexPtToKeep_4pps.size());
				setAllIndexPointToKeep_4path.addAll(pps.vIndexPtToKeep_4pps);

			} else {
				// La simplification de la pps en cours a échoué : vPPS a reçu de nouvelle sous-pps a tenter de simplifier
				// on indique que la boucle est plus longue que prévu initialement, et on poursuit la boucle
				assert(vPPS.size() > nbPPS);
				Logger.log_DEBUG2("    -> " + (vPPS.size() - nbPPS) + " nouvelles PPS à tenter de simplifier");
				nbPPS = vPPS.size();
				
				setPathREFMalReduit.add(pps.pathREF);
			}
		}
		return setAllIndexPointToKeep_4path;
	}


	// Le vecteur en sortie peut eventuellement comporter des doublons : à l'appelant de le gérer
	private static boolean simplifyPPS(PortionPathASimplifier pps, ArrayList<PortionPathASimplifier> vPPS, SimpleGridSPI spiPath) {
		assert (pps.status == STATUS_PPS.NOT_COMPUTED);
		assert (pps.iDeb<= pps.iFin);

		// Point à conserver pour ce PPS
		TIntArrayList vIndexPtToKeep_4pps = new TIntArrayList();

		// On conserve forcément les extrémités du PPS
		// (la version douglasPeuckerReduction_recurs() de l'algo DP ne les renvoie pas)
		vIndexPtToKeep_4pps.add(pps.iDeb);
		vIndexPtToKeep_4pps.add(pps.iFin);

		// Cas d'arrêt : 2 points consécutifs : rien à simplifier
		if (pps.iDeb>= pps.iFin-1) {
			pps.status = STATUS_PPS.OK;
			pps.setVIndexPointToKeep(vIndexPtToKeep_4pps);
			return true;
		}
			

		// On calcule les points que l'on conserve sur le reste du PPS
		UtilsGeom.douglasPeuckerReduction_recurs(pps.pathREF.getVJunction(), pps.iDeb, pps.iFin, pps.tolerance, vIndexPtToKeep_4pps);
		
		// Détection d'éventuelles intersections créées
		vIndexPtToKeep_4pps.sort();
		if (isThereNewIntersection(pps, vIndexPtToKeep_4pps, vPPS, spiPath)){
			
			pps.status = STATUS_PPS.KO;

			// Stratégie 1 : coupure en 2 sous-pps égales
			PortionPathASimplifier pps_new1 = pps.getCopy();
			PortionPathASimplifier pps_new2 = pps.getCopy();
			pps_new1.iFin = (pps.iFin+pps.iDeb)/2;
			pps_new2.iDeb = (pps.iFin+pps.iDeb)/2;
			pps_new1.computeBoundingBox();
			pps_new2.computeBoundingBox();
			
			// On ajoute ces 2 nouvelles pps au vecteur des pps du path
			vPPS.add(pps_new1);
			vPPS.add(pps_new2);
			return false;


		} else {

			pps.status = STATUS_PPS.OK;
			pps.setVIndexPointToKeep(vIndexPtToKeep_4pps);
			return true;
		}
	}

	private static boolean isThereNewIntersection(PortionPathASimplifier pps, TIntArrayList vIndexPtToKeep_4pps, ArrayList<PortionPathASimplifier> vPPS, SimpleGridSPI spiPath) {
		// 2 tests : d'abord au sein du meme path puis avec les autres path
		return isThereNewIntersection_withSamePath(pps, vIndexPtToKeep_4pps, vPPS) ||
			   isThereNewIntersection_withOtherPath(pps, vIndexPtToKeep_4pps, spiPath);
	}


	private static boolean isThereNewIntersection_withSamePath(PortionPathASimplifier pps, TIntArrayList vIndexPtToKeep_4pps, ArrayList<PortionPathASimplifier> vPPS) {

		// Tout d'abord, test au sein même de la pps
		if (isThereNewIntersect_withinPPS(pps, vIndexPtToKeep_4pps))
			return true;

		// Puis avec les autres pps du path
		// Ce qui est compliqué, c'est que le path n'a pas encore été simplifié réellement (il est en cours de calcul)
		//  mais que certaines de ses PPS ont été simplifiée : il faut tester les intersections avec les points originels du path
		//  si la portion n'a pas été simplifiée, et avec les points simplifiés stockés dans les PPS qui ont été traitées.
		// Pour cela on parcourt toutes les PPS du path, et selon leur status, on teste sur les points originels ou les points simplifiés ...
		int nbPPS = vPPS.size();
		for (int i=0 ; i<nbPPS ; i++) {
			PortionPathASimplifier pps2 = vPPS.get(i);
			if (pps==pps2) continue; // cf. testé ci-avant
			if (isThereNewIntersect_between2PPS(pps, vIndexPtToKeep_4pps, pps2))
				return true;
		}
		return false;
	}

	// Test d'intersection / superposition au sein de la même pps (en cours de calcul)
	private static boolean isThereNewIntersect_withinPPS(PortionPathASimplifier pps, TIntArrayList vIndexPtToKeep_4pps) {
		ArrayList<A_Junction> vJ;
		
		if (!bDuringTrt)
			// Mode Pre-traitement, on regarde les coordonnées REF
			vJ = pps.pathREF.getVJunction();
		else
			// Mode Durant-traitement, on regarde les coordonnées DER
			vJ = pps.pathREF.getPathDER().getVJunction();
		
		int nbPt = vIndexPtToKeep_4pps.size();
		for (int i=0; i<nbPt-1; i++) {
			A_Junction j1 = vJ.get(vIndexPtToKeep_4pps.get(i));
			A_Junction j2 = vJ.get(vIndexPtToKeep_4pps.get(i+1));

			for (int j=i+1; j<nbPt-1; j++) {
				A_Junction j3 = vJ.get(vIndexPtToKeep_4pps.get(j));
				A_Junction j4 = vJ.get(vIndexPtToKeep_4pps.get(j+1));
				if (UtilsGeom.areSegmentInternallyIntersected(j1, j2, j3, j4) || UtilsGeom.areSegmentSuperposed(j1, j2, j3, j4)) {
					Logger.log_DEBUG2("  -> la portion " + pps +  " crée de nouvelles intersections -> au sein d'elle-même");
					return true;
				}
			}
		}
		return false;

	}

	// Test d'intersection / superposition entre 2 pps du même path
	private static boolean isThereNewIntersect_between2PPS(PortionPathASimplifier pps1, TIntArrayList vIndexPtToKeep_4pps1, PortionPathASimplifier pps2) {
		assert(pps1.status == STATUS_PPS.NOT_COMPUTED); // pps1 est en cours de calcul
		assert(pps1 != pps2); // les 2 pps doivent etre <>
		assert(pps1.pathREF == pps2.pathREF);

		if (pps2.status == STATUS_PPS.KO)
			// rien à calculer, cette pps2 n'est pas à prendre en compte, elle a été découpée en plusieurs sous-pps plus loin dans le vecteur de pps global du path
			return false;
		
		
		ArrayList<A_Junction> vJ;
		if (!bDuringTrt)
			// Mode Pre-traitement, on regarde les coordonnées REF
			vJ = pps1.pathREF.getVJunction();
		else
			// Mode Durant-traitement, on regarde les coordonnées DER
			vJ = pps1.pathREF.getPathDER().getVJunction();
		
			
		int nbPt1 = vIndexPtToKeep_4pps1.size();
		for (int i=0; i<nbPt1-1; i++) {
			A_Junction j1 = vJ.get(vIndexPtToKeep_4pps1.get(i));
			A_Junction j2 = vJ.get(vIndexPtToKeep_4pps1.get(i+1));

			// Avec quels segments doit on tester ?
			if (pps2.status == STATUS_PPS.NOT_COMPUTED) {
				// on parcourt les points non encore simplifié de pps2
				for (int j=pps2.iDeb; j<=pps2.iFin-1 ; j++) {
					A_Junction j3 = vJ.get(j);
					A_Junction j4 = vJ.get(j+1);

					if (UtilsGeom.areSegmentInternallyIntersected(j1, j2, j3, j4) || UtilsGeom.areSegmentSuperposed(j1, j2, j3, j4)) {
						Logger.log_DEBUG2("  -> la portion " + pps1 +  " crée de nouvelles intersections -> avec " + pps2 + " (non encore simplifiée)");
						return true;
					}
				}

			} else {
				// on parcourt les points simplifiés de pps2
				TIntArrayList vIndexPtToKeep_4pps2 = pps2.getVIndexPointToKeep();
				int nbPt2 = vIndexPtToKeep_4pps2.size();
				for (int j=0; j<nbPt2-1 ; j++) {
					A_Junction j3 = vJ.get(vIndexPtToKeep_4pps2.getQuick(j));
					A_Junction j4 = vJ.get(vIndexPtToKeep_4pps2.getQuick(j+1));

					if (UtilsGeom.areSegmentInternallyIntersected(j1, j2, j3, j4) || UtilsGeom.areSegmentSuperposed(j1, j2, j3, j4)) {
						Logger.log_DEBUG2("  -> la portion " + pps1 +  " crée de nouvelles intersections -> avec " + pps2 + " (déjà simplifiée)");
						return true;
					}
				}
			}
		}
		return false;
	}


	// Détermine si vIndexPtToKeep_4pps de la pps en cours a des segments en intersection/superposition
	//  avec les segments des autres path
	// SIOUX : durant le traitement appelant, on modifie les path, et pourtant on ne met pas
	//  a jour le SPI -> en fait, les path bougent peu, et on interroge le SPI avec
	//  un rectangle englobant légèrement plus grand par sécurité
	// Rq : vIndexPtToKeep_4pps doit être trié au préalable !
	private static boolean isThereNewIntersection_withOtherPath(PortionPathASimplifier pps, TIntArrayList vIndexPtToKeep_4pps, SimpleGridSPI spiPath) {
			
		ArrayList<A_Junction> vJ;
		if (!bDuringTrt)
			// Mode Pre-traitement, on regarde les coordonnées REF
			vJ = pps.pathREF.getVJunction();
		else
			// Mode Durant-traitement, on regarde les coordonnées DER
			vJ = pps.pathREF.getPathDER().getVJunction();

		Rect_d rectEnglobSegTest = new Rect_d();

		// Pour chaque segment simplifié : on teste la présence d'intersection / superposition avec les autres path
		int nbPt = vIndexPtToKeep_4pps.size();
		for (int i=0; i<nbPt-1; i++) {

			A_Junction j1 = vJ.get(vIndexPtToKeep_4pps.getQuick(i));
			A_Junction j2 = vJ.get(vIndexPtToKeep_4pps.getQuick(i+1));

			rectEnglobSegTest.setCoordFrom(j1);
			rectEnglobSegTest.extendToPoint(j2);
			rectEnglobSegTest.expand(tolerance_reel_m_MAX*2, tolerance_reel_m_MAX*2);

			// Ce vecteur contiendra des PathREF si pre-trt et PathDER si Durant trt (ce n'est pas le meme spi qui est fourni dans chaque cas)
			ArrayList<A_Path> vPathAlentours = (ArrayList) spiPath.getObjectsThatMayIntersectWith(rectEnglobSegTest);

			// parcours des path alentours
			int nbPathAlentour = vPathAlentours.size();
			for (int k=0 ; k<nbPathAlentour ; k++) {
				// p2 est de type PathREF si pre-trt et PathDER si Durant trt (ce n'est pas le meme spi qui est fourni dans chaque cas)
				A_Path p2 = vPathAlentours.get(k);

				// Le test au sein du même path fait l'objet d'un traitement spécial
				if (p2==pps.pathREF)
					continue;

				// Test simple de bounding box
				if (!UtilsGeom.areRectIntersected(pps.boundingBox, p2.boundingBox))
					continue;

				ArrayList<A_Junction> vJ2 = p2.getVJunction();
				int nbJ2 = vJ2.size();
				for (int j=0; j<nbJ2-1; j++) {

					A_Junction j3 = vJ2.get(j);
					A_Junction j4 = vJ2.get(j+1);

					// premier test simple de bounding box
					if (!UtilsGeom.areSegPotentiallyIntersected(j1, j2, j3, j4))
						continue;

					// puis test d'intersection
					if (UtilsGeom.areSegmentInternallyIntersected(j1, j2, j3, j4) || UtilsGeom.areSegmentSuperposed(j1, j2, j3, j4)) {
						Logger.log_DEBUG2("  -> la portion " + pps +  " crée de nouvelles intersections -> avec autre path " + p2);
						return true;
					}
				}
			}
		}
		return false;
	}


	private static ArrayList<PortionPathASimplifier> decomposePathEnPPS(PathREF path) {

		ArrayList<PortionPathASimplifier> vPPS = new ArrayList<PortionPathASimplifier>();

		ArrayList<JunctionREF> vJREF = path.getVJunctionREF();
		int nbJunction = vJREF.size();

		// Calcul de la tolérance reelle du path

		// les vérifications qui suivent ont été lancée avant la simplification des path
		//  donc on ne gère pas l'erreur proprement
		assert (path.getEchelleGeneralization()!=null);
		assert (path.getContrainteGeom()!=null);

		double echelleCiblePath_inv = path.getEchelleGeneralization().echelle_inv;
		double tolerance_reel_m = (/*path.getContrainteGeom().epaisseur_dissymetrie_mm +*/ path.getContrainteGeom().epaisseurTrait_papier_mm) * params.factor_SimplifPath_tolerance/1000.0 * echelleCiblePath_inv;

		int indexDeb, indexFin;
		indexFin = 0;

		while (indexFin<nbJunction-1) {
			indexDeb = indexFin;
			indexFin = getNextNonStd_orLast(indexDeb, vJREF);
			vPPS.add (new PortionPathASimplifier(path, indexDeb, indexFin, tolerance_reel_m));
		}

		return vPPS;
	}


	static private int getNextNonStd_orLast (int iDeb, ArrayList<JunctionREF> vJREF) {
		int nbJunction = vJREF.size();
		int iNextNonStd;
		iNextNonStd = iDeb+1;
		while (vJREF.get(iNextNonStd).isStd() && iNextNonStd < nbJunction-1)
			iNextNonStd++;
		return iNextNonStd;
	}


	private static void redecoupePath_std() {
		Logger.log_INFO2(" -> Redécoupage des path pour que chaque segment soit plus petit que " + params.factor_RedecoupPath_lgSegMax_std + " x épaisseur_Path");
		if (params.factor_RedecoupPath_lgSegMax_std <= 0) {
			Logger.log_INFO2("  -> rien à redécouper du fait des paramètres utilisateur");
			return;
		}
			
		for (PathREF path : vPathREFaTraiter) {

			// longueur minimal des segment du path : dépendent de sa largeur (et donc de l'échelle etc.)
			
			// il arrive que des path vituels soient présent avec une echelle = 0
			// ils viennent des segment virtuel créés pour relier des nodes en doublon fusionnés
			// cf. PathNodeCreator.fusioneNode()
			if (path.getEchelleGeneralization().echelle_inv == 0)
				continue;
			
			double lgMax = params.factor_RedecoupPath_lgSegMax_std * (path.getContrainteGeom().epaisseurTrait_papier_mm) /1000.0 * path.getEchelleGeneralization().echelle_inv;

			ArrayList<JunctionREF> vJREF = path.getVJunctionREF();
			int nbJ = vJREF.size();
			ArrayList<JunctionREF> vJREF_new = new ArrayList<JunctionREF>(nbJ);
			
			vJREF_new.add(vJREF.get(0));

			for (int i=0; i<nbJ-1 ; i++) {
				JunctionREF j1 = vJREF.get(i);
				JunctionREF j2 = vJREF.get(i+1);		

				// Mnt, voyons si le segment en cours est trop grand
				double dist = j1.distTo(j2);
				if (dist > lgMax) {
					// segment trop long : on doit découper

					// nb de point à ajouter
					int nbPtToAdd = (int) (dist/lgMax);
					Logger.log_DEBUG2("Redécoupage path : " + path + " -> le segment " + i + "->" + (i+1) + " doit être redécoupé en " + nbPtToAdd + " points, cf. lg = " + dist + " / " + lgMax);

					for (int j=0; j<nbPtToAdd ; j++) {
						double ratio = ((double)j+1)/(nbPtToAdd+1);
						double newX = j1.x + (j2.x-j1.x)*ratio;
						double newY = j1.y + (j2.y-j1.y)*ratio;
						JunctionREF jREF = new JunctionREF(newX, newY, TypeJunction.STD);
						jREF.addPathContenant(path);
						jREF.addInfoDebug("cree par redecoupePath()");
						vJREF_new.add(jREF);

						// on ajoute les nouvelles junctions dans le vecteur global
						vAllJunctionREF.add(jREF);
					}
				}
				vJREF_new.add(j2);
			}

			path.setVJunctionREF(vJREF_new);
		}
	}
	
	private static void redecoupePath_procheNode (SimpleGridSPI spi) {
		Logger.log_INFO2(" -> Redécoupage des path pour que chaque segment soit plus petit que " + params.factor_RedecoupPath_lgSegMax_std + " x épaisseur_Path dans une zone proche d'un node (" +  params.factor_RayonAction_decoupSeg_procheNode + " x son rayon)");
		boolean bDecoupPath_procheNode = params.factor_RedecoupPath_lgSegMax_procheNode > 0 && params.factor_RayonAction_decoupSeg_procheNode > 0;
		if (!bDecoupPath_procheNode) {
			Logger.log_INFO2("  -> rien à redécouper du fait des paramètres utilisateur");
			return;
		}
		double rayonActionNode = params.factor_RayonAction_decoupSeg_procheNode;

		// Creation d'un spi pour les nodes
		spi.clear();
		double largestRayonNode = 0;
		for (JunctionREF node : vAllJunctionREF) {
			if (node.isNode()) {
				spi.addPoint(node);
				largestRayonNode = Math.max(largestRayonNode, 0.5 * node.nodeData.contrainteGeom.diametre_papier_mm/1000.0 * node.nodeData.echelleGeneralization.echelle_inv);
			}
		}

			
		for (PathREF path : vPathREFaTraiter) {

			// longueur minimal des segment du path : dépendent de sa largeur (et donc de l'échelle etc.)
			
			// il arrive que des path vituels soient présent avec une echelle = 0
			// ils viennent des segment virtuel créés pour relier des nodes en doublon fusionnés
			// cf. PathNodeCreator.fusioneNode()
			if (path.getEchelleGeneralization().echelle_inv == 0)
				continue;
			
			double lgMax = params.factor_RedecoupPath_lgSegMax_procheNode * (path.getContrainteGeom().epaisseurTrait_papier_mm) /1000.0 * path.getEchelleGeneralization().echelle_inv;

			ArrayList<JunctionREF> vJREF = path.getVJunctionREF();
			int nbJ = vJREF.size();
			ArrayList<JunctionREF> vJREF_new = new ArrayList<JunctionREF>(nbJ);
			

			vJREF_new.add(vJREF.get(0));

			for (int i=0; i<nbJ-1 ; i++) {
				JunctionREF j1 = vJREF.get(i);
				JunctionREF j2 = vJREF.get(i+1);
				boolean modeProcheNode; // true si decoup a cause de proche node, false sinon
				
				// Déterminons si le segment est proche d'un node
				boolean bPathProcheNode = false;
				
				Rect_d rectRechNode = new Rect_d(j1, j2);
				rectRechNode.expand(rayonActionNode * largestRayonNode, rayonActionNode * largestRayonNode);
				ArrayList<JunctionREF> vNodeProche = (ArrayList) spi.getObjectsThatMayIntersectWith(rectRechNode);
				for (JunctionREF node : vNodeProche) {
					double rayonNode = 0.5 * node.nodeData.contrainteGeom.diametre_papier_mm/1000.0 * node.nodeData.echelleGeneralization.echelle_inv;
					double rayonDecoupNode = rayonActionNode * rayonNode;
					if (UtilsGeom.getDistancePtSegment(j1, j2, node) <= rayonDecoupNode) {
						// le segment est suffisament proche d'un node pour necessiter un decoupage
						bPathProcheNode = true;
						break;
					}
				}

				// Mnt, voyons si le segment en cours est trop grand et proche d'un node
				double lgSeg = j1.distTo(j2);

				if (bPathProcheNode && lgSeg>lgMax) {
					// nb de point à ajouter
					int nbPtToAdd = (int) (lgSeg/lgMax);
					Logger.log_DEBUG2("Redécoupage path : " + path + " -> le segment " + i + "->" + (i+1) + " doit être redécoupé en " + nbPtToAdd + " points, cf. lg = " + lgSeg + " / " + lgMax);

					for (int j=0; j<nbPtToAdd ; j++) {
						double ratio = ((double)j+1)/(nbPtToAdd+1);
						double newX = j1.x + (j2.x-j1.x)*ratio;
						double newY = j1.y + (j2.y-j1.y)*ratio;
						JunctionREF jREF = new JunctionREF(newX, newY, TypeJunction.STD);
						// si le segment est tres long, les nouveaux points risque d'être créés très loin du node !
						// mais tant pis ...
						jREF.addPathContenant(path);
						jREF.addInfoDebug("cree par redecoupePath()");
						vJREF_new.add(jREF);

						// on ajoute les nouvelles junctions dans le vecteur global
						vAllJunctionREF.add(jREF);
					}
				}
				
				vJREF_new.add(j2);
			}

			path.setVJunctionREF(vJREF_new);
		}
	}
/*
	private static void redecoupePath_procheNode(SimpleGridSPI spiJ) {
		
		
		//**********************************************************************
		// Pour chaque path, decoupage au niveau du rayon d'influence totale
		//  et du rayon d'influence nulle
		for (PathREF path : vPathREFaTraiter) {

			int nbNodeconnected = path.getNbNodeConnected();
			for (int i=0; i<nbNodeconnected ; i++) {
				A_Junction node = path.getNodeConnected(i);

				double rayon_final = 0.5 * node.nodeData.contrainteGeom.diametre_papier_mm/1000.0 * node.nodeData.echelleGeneralization.echelle_inv;
				double rayonInfluenceTotale = rayon_final * node.nodeData.contrainteGeom.influenceTotale;
				double rayonInfluenceNulle = rayonInfluenceTotale * node.nodeData.contrainteGeom.influenceNulle;

//				redecoupePath_thisCircle (path, node, rayonInfluenceTotale);
//				redecoupePath_thisCircle (path, node, rayonInfluenceNulle);

				// on ne coupe qu'en 1 point, finalement (sinon ca crée trop de nouveaux points)
				//  entre les 2 rayons d'influence, mais plus pres du rayon d'influence totale
				redecoupePath_thisCircle (path, node, (2*rayonInfluenceTotale + rayonInfluenceNulle)/3, spiJ);
			}
		}
	}

	private static void redecoupePath_thisCircle(PathREF path, Point_d center, double rayon, SimpleGridSPI spiJ) {

		// Recherche des segments du path qui intersecte le cercle, puis decoupage

		Rect_d circle = new Rect_d(center, rayon*2);
		double[] tabCoordIntersect = new double[4];

		ArrayList<JunctionREF> vJREF = path.getVJunction();
		ArrayList<JunctionREF> vJREF_new = new ArrayList<JunctionREF>();
		int nbJ = vJREF.size();

		vJREF_new.add(vJREF.get(0));

		for (int i=0; i<nbJ-1 ; i++) {
			JunctionREF j1 = vJREF.get(i);
			JunctionREF j2 = vJREF.get(i+1);

			double dist1 = j1.distTo(center);
			double dist2 = j2.distTo(center);

			// tant pis pour les cas tordus ou un segment est a cheval 2 fois sur le cercle avec 2 intersections ...
			if ( (dist1 < rayon && dist2 > rayon) || (dist1 > rayon && dist2 < rayon) ) {
				// segment à cheval sur le cercle : on le découpe
				int nbIntersect = UtilsGeom.computeIntersect_Ellipse_Segment(circle, new Segment_d(j1, j2), tabCoordIntersect);
				
				// il se peut qu'il n'y ait aucune intersection (voire 2) a cause d'erreurs d'arrondi
				if (nbIntersect>0) {

					Point_d ptIntersect = new Point_d(tabCoordIntersect[0], tabCoordIntersect[1]);

					// on ne crée la nouvelle junction que s'il n'en existe pas une à proximité (seuil = rayon/x)
					// notamment, cela permet de ne pas avoir de junctions superposees si on lance 2 fois ce traitement
					if (j1.distTo(ptIntersect) > rayon/4 && j2.distTo(ptIntersect) > rayon/4) {

						// On rajoute ce test, car il est arrivé des cas bizares ou on tombe pile sur un autre point du meme path
						// (cas ou le path repasse par lui meme en se superposant, c'est censé etre un bug, mais bon)
						if (spiJ.isThisPointInSPI(ptIntersect))
							//System.out.println("============== " + ptIntersect.x + "   " + ptIntersect.y);
//							spiJ=spiJ;
							;
						else {
							JunctionREF jREF = new JunctionREF(ptIntersect.x, ptIntersect.y, TypeJunction.STD, path);
							jREF.addInfoDebug("cree par redecoupe Path proche Node");
							vJREF_new.add(jREF);
							spiJ.addPoint(jREF);

							// on ajoute les nouvelles junctions dans le vecteur global
							vAllJunctionREF.add(jREF);
						}
					}
				}
			}
			vJREF_new.add(j2);
		}

		path.setVJunctionREF(vJREF_new);

	}
*/

	// Assure que chaque path reliant 2 node directement comporte a minima n junction
	//  c'est pour un bon ecartement des double lignes entre nodes, donc on ne fait ca que
	//  dans le cas ou les 2 nodes ont plus que 2 path qui partent !)
	private static void redecoupeAllPath_NodeNode() {
		int NB=0;
		for (PathREF path : vPathREFaTraiter) {
			if (path.from().isNode() && path.from().getNbPathContenant()>=2 &&
				path.to().isNode()   && path.to().getNbPathContenant()>=2) {
				while (path.getNbJunction() < 2 + params.nbMinPointEntre2Node) {
					redecoupePath_NodeNode(path);
					NB++;
				}
			}
		}
		Logger.log_INFO2(" -> nb point ajouté par redecoupage path entre 2 node : " + NB);
	
	}
	private static void redecoupePath_NodeNode(PathREF path) {
		// On cherche le segment le plus grand, c'est lui qui sera sous-découpé
		int indexSegPlusLong = getIndexSegPlusGrand(path);
		JunctionREF j1 = path.vJunctionREF.get(indexSegPlusLong);
		JunctionREF j2 = path.vJunctionREF.get(indexSegPlusLong+1);
		double newX = (j1.x + j2.x)/2;
		double newY = (j1.y + j2.y)/2;
		JunctionREF jREF = new JunctionREF(newX, newY, TypeJunction.STD, path);
		path.vJunctionREF.add(indexSegPlusLong+1, jREF);
		jREF.addInfoDebug("cree par redecoupe Path entre Node");
		vAllJunctionREF.add(jREF);
	}
	private static int getIndexSegPlusGrand(PathREF path) {
		if (path.vJunctionREF.size()==2)
			// 1 seul segment ...
			return 0;
		double distMax = Double.NEGATIVE_INFINITY;
		int indexDistMax = -1;
		int nbJ = path.vJunctionREF.size();
		for (int i=0; i<nbJ-1 ; i++) {
			JunctionREF j1 = path.vJunctionREF.get(i);
			JunctionREF j2 = path.vJunctionREF.get(i+1);
			double dist = j1.distTo(j2);
			if (dist>distMax) {
				distMax = dist;
				indexDistMax = i;
			}
		}
		return indexDistMax;
	}



	private enum STATUS_PPS {NOT_COMPUTED, OK, KO};
	static private class PortionPathASimplifier {
		public PathREF pathREF;
		public int iDeb, iFin;
		public double tolerance;
		STATUS_PPS status;
		
		private TIntArrayList vIndexPtToKeep_4pps = null; // les index des points à garder pour cette pps
		public void setVIndexPointToKeep(TIntArrayList v) {
			v.sort();
			this.vIndexPtToKeep_4pps = v;
		}
		public TIntArrayList getVIndexPointToKeep() {
			return vIndexPtToKeep_4pps;
		}

		public PortionPathASimplifier(PathREF p, int iDeb, int iFin, double tolerance) {
			this.pathREF=p;
			this.iDeb=iDeb;
			this.iFin=iFin;
			this.tolerance=tolerance;
			status = STATUS_PPS.NOT_COMPUTED;
			computeBoundingBox();
		}
		

		public Rect_d boundingBox;
		
		final public void computeBoundingBox() {
			
			ArrayList<A_Junction> vJ;
			if (!bDuringTrt)
				// Mode Pre-traitement, on regarde les coordonnées REF
				vJ = pathREF.getVJunction();
			else
				// Mode Durant-traitement, on regarde les coordonnées DER
				vJ = pathREF.getPathDER().getVJunction();

			boundingBox = new Rect_d(vJ.get(iDeb));
			for (int i=iDeb+1; i<=iFin ; i++)
				boundingBox.extendToPoint(vJ.get(i));
		}


		public PortionPathASimplifier getCopy() {return new PortionPathASimplifier(this.pathREF, this.iDeb, this.iFin, this.tolerance);}

		@Override
		public String toString() {return "" + iDeb + "->" + iFin + "(" + tolerance + ")";}

	}
}
